package com.剑指offer一;

import java.util.*;

/**
 * TODO(剑指 Offer 32 - III. 从上到下打印二叉树 III)
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * @author leon
 * @date 2021年12月21日 19:55
 */
public class LevelOrder3 {
    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            if(root == null){
                return ans;
            }
            // 队列
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                // 用双端队列存储
                LinkedList<Integer> list = new LinkedList<>();
                while (size-->0){
                    TreeNode node = queue.poll();
                    // 判断奇偶层
                    if(ans.size()%2==0){
                        list.addLast(node.val);
                    }else {
                        list.addFirst(node.val);
                    }
                    if(node.left!=null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }

                ans.add(list);
            }
            return ans;
    }
}
